package string;

/**
 * @Author: 海琳琦
 * @Date: 2022/2/1 15:49
 * 不要使用辅助空间，空间复杂度要求为$O(1)$。
 */
public class ReverseWords {

    /**
     * 耗费额外空间
     * @param s
     * @return
     */
    public static String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        String[] split = s.trim().split(" ");
        for (int i = split.length - 1; i >= 0; i--) {
            if (!split[i].equals("")) {
                if (i != 0) {
                    sb.append(split[i]);
                    sb.append(" ");
                } else {
                    sb.append(split[i]);
                }
            }
        }
        return sb.toString();
    }

    /**
     * 原地操作
     * @param s
     * @return
     */
    public static String reverseWords1(String s) {
        //1、移除多余的空格
        StringBuilder builder = removeSpace(s);
        //2、翻转整个字符串
        reverseString(builder, 0, builder.length() - 1);
        System.out.println(builder.toString());
        //3、翻转每个单词
        int start = 0;
        int end = 1;
        while (start < builder.length()) {
            while (end < builder.length() && builder.charAt(end) != ' ') {
                end++;
            }
            //翻转单个单词
            reverseString(builder, start, end - 1);
            start = end + 1;
            end = start + 1;
        }
        return builder.toString();
    }

    private static void reverseString(StringBuilder s, int start, int end) {
        while (start < end) {
            char c = s.charAt(start);
            s.setCharAt(start, s.charAt(end));
            s.setCharAt(end, c);
            start++;
            end--;
        }
    }

    public static StringBuilder removeSpace(String s) {
        int firstIndex = 0;
        int endIndex = s.length() - 1;
        //移除字符串首前的空格
        while (s.charAt(firstIndex) == ' ') {
            firstIndex++;
        }
        //移除字符串末尾的空格
        while (s.charAt(endIndex) == ' ') {
            endIndex--;
        }
        StringBuilder sb = new StringBuilder();
        //移除字符串间多余的空格（有空格只取一个）
        while (firstIndex <= endIndex) {
            if (s.charAt(firstIndex) != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(s.charAt(firstIndex));
            }
            firstIndex++;
        }
        return sb;
    }


    public static void main(String[] args) {
        System.out.println(reverseWords("  a good     example "));
    }
}
